λ¬Έμ
BOJ - λλ μΉκ΅¬κ° μ λ€(Large)
π Logic
π CODE
μ½λ 보기/μ κΈ°π«
import java.io.*;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String book = br.readLine().replaceAll("\\d", "");
String keyword = br.readLine();
System.out.println(KMP(book, keyword) ? 1 : 0);
}
public static int[] computeTable(String book) {
int n = book.length();
int[] table = new int[n];
int idx = 0;
for (int i = 1; i < n; i++) {
// λ¬Έμκ° μΌμΉνλ©΄, μ°μμ μΌλ‘ μΌμΉν λκΉμ§ νμ
// μΌμΉνμ§ μλ κ²½μ° μ΄μ idxμ tableκ°μ idxλ‘
while (idx > 0 && book.charAt(i) != book.charAt(idx))
idx = table[idx - 1];
if (book.charAt(i) == book.charAt(idx)) {
idx += 1;
table[i] = idx;
}
}
return table;
}
public static boolean KMP(String book, String keyword) {
int n1 = book.length();
int n2 = keyword.length();
int[] table = computeTable(book);
boolean found = false;
int idx = 0; // νμ¬ λμλλ κΈμ μ
for(int i = 0; i < n1; i++) {
// ν€μλμ idxλ² κΈμμ κ΅κ³Όμμ ν΄λΉ κΈμκ° λΆμΌμΉν κ²½μ°,
// νμ¬ λμλ κΈμμ μλ₯Ό table[idx-1]λ²μΌλ‘ μ€μΈλ€.
while (idx > 0 && book.charAt(i) != keyword.charAt(idx))
idx = table[idx - 1];
// κΈμκ° λμλ κ²½μ°
if (book.charAt(i) == keyword.charAt(idx)) {
if (idx == n2 - 1) {
found = true;
break;
} else
idx += 1;
}
}
return found;
}
}
βοΈ Review
- μ κ·ννμμΌλ‘ μ κ·Όνλ€κ° μμ²λ μκ°μ΄κ³Όλ₯Ό λ§λ₯λ¨λ € λ¬΄μ¨ μκ³ λ¦¬μ¦μ μ°λμ§ λ΄€λ€.
- KMP μκ³ λ¦¬μ¦μ μ μ΄ν΄νμ§ λͺ»ν΄μ νμ λ€μ μ΄ν΄ν νμ λ‘μ§μ μ μ΄λ΄μΌ ν κ² κ°λ€.